Shifts of digital data representing binary numbers towards increased significance or towards decreased significance are regarded as shifts left or as shifts right, respectively, in the more commonly used convention for arithmetic processing. Binary- place shifts are commonly encountered in multiplication, division, the taking of roots by synthetic division, and other arithmetic procedures.
Digit-serial arithmetic procedures share some of the attributes of the more common procedures employing serial (or bit-serial) arithmetic and employing parallel arithmetic. Each arithmetic word is divided into digits each of a few bits--e.g. three, four, five or six bits per digit. The bits within each digit are processed in parallel with each other, but the digits are processed serially respective to each other. The serial processing is done beginning with the least significant bit, and the digits are also supplied in order of increasing significance. Digit-serial arithmetic allows the use of simpler digital hardware than parallel arithmetic, approaching the simplicity of that for bit-serial arithmetic. At the same time, the parallel processing of each digit speeds processing and reduces the latency (delay) in processing. So, often the most favorable trade-off of speed versus digital hardware requirements is found using digit-serial arithmetic.
In more recent times most digital arithmetic circuitry is constructed in monolithic integrated circuit form and indeed in very large scale integrated (VLSI) circuit form. The layout of individual circuits on the monolithic die is an onerous task to do "by hand" in a VLSI circuit, so the task is performed by machine using an apparatus generally known as a "silicon compiler". The compiler is a computer containing within its memory a library of elemental circuit structures that are used as "building blocks" to be combined according to instructions from a human operator to form complex circuit structures. These elemental circuit structures repose within respective basic cells or tiles of standard dimensions that can be arranged in a more or less regular mosaic to form the more complex circuitry.
Generally, the basic cells are rectangular. Rectangular shapes lend themselves to close-packed tiling without intervening spaces and fit well within the rectangular boundaries of the monolithic die. Also rectangular cells can be readily laid out with a perversion, an inversion or both on the surface of the die.
The practical problem one encounters with more straightforward shifter designs is that they do not lend themselves to dissection into a restricted number of basic cells. This is in part because left shifters and right shifters tend not to use the same basic cells. In large measure, however, the problem with reducing the number of basic cells comes about because of the n respective bits in each digit being processed in respective pipeline structures. The n pipeline structures resist being tiled alike, because interconnections to load the successive stages in each of these pipeline structures are dissimilar. Accordingly, there is a strong tendency towards an undesirable n-fold increase in the number of basic cells associated with digit-serial processing, and there are attendant problems arriving at an architecture in which the basic cells can be arranged in a compact stack of bit-slice cells that lends itself to being in close cascade connection with other portions of a monolithic integrated circuit.
There is an underlying desire in regard to the invention to tile the n pipelines involved in a digit-serial shifter using the same set of basic cells for each pipeline, rather than n sets of basic cells one for each pipeline.